package com.atwy.graph.directedgraph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: 小王子火
 * @Date: 2022/3/18
 * 深度优先的顶点排序：深度优先搜索正好只会访问每个顶点一次。
 * 如果将dfs()方法中的参数顶点保存在一个数据结构中，遍历这个数据结构就能
 * 访问到图中每个顶点，遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是之后保持的。
 * 1、前 序： 在递归调用之前将顶点加入队列。
 * 2、后 序： 在递归调用之后将顶点加入队列。
 * 3、逆后序：在递归调用之后将顶点压入栈。
 */
public class DepthFirstOrder {

    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;
    /**
     * 所有顶点的前序排列
     */
    private Queue<Integer> pre;
    /**
     * 所有顶点的后序排列
     */
    private Queue<Integer> post;
    /**
     * 所有顶点的逆后序排列
     */
    private Stack<Integer> reversePost;

    public DepthFirstOrder(IDigraph graph) {
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new Stack<>();

        marked = new boolean[graph.V()];
        for (int s=0;s<graph.V();s++){
            if(!marked[s]){
                dfs(graph,s);
            }
        }
    }

    private void dfs(IDigraph graph, int v) {
        // 在递归之前加入
        pre.offer(v);
        marked[v] = true;
        for(int w : graph.adj(v)){
            if(!marked[w]){
                dfs(graph,w);
            }
        }
        // 在递归之后加入
        post.offer(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre(){
        return pre;
    }

    public Iterable<Integer> post(){
        return post;
    }

    public Iterable<Integer> reversePost(){
        return reversePost;
    }
}
